package summary;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/13 15:13
 * https://leetcode-cn.com/problems/maximum-binary-tree/
 */
public class Title654 {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return traversal(nums, 0, nums.length);
    }

    /**
     * [start, end)
     * @param nums
     * @param start
     * @param end
     * @return
     */
    public TreeNode traversal(int[] nums, int start, int end) {
        if (end - start == 0) {
            return null;
        }
        //1、遍历寻找最大值
        int maxIndex = 0;
        for (int i = start; i < end; i++) {
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }
        TreeNode root = new TreeNode(nums[maxIndex]);
        if (end - start == 1) {
            return root;
        }
        int leftStart = start;
        int leftEnd = maxIndex;
        int rightStart = maxIndex + 1;
        int rightEnd = end;
        root.left = traversal(nums, leftStart, leftEnd);
        root.right = traversal(nums, rightStart, rightEnd);
        return root;
    }




    public TreeNode constructMaximumBinaryTree1(int[] nums) {
        return dfs(nums, 0, nums.length);
    }

    private TreeNode dfs(int[] nums, int start, int end) {
        if (start == end) {
            return null;
        }
        int maxIndex = start;
        for (int i = start + 1; i < end; i++) {
            if (nums[maxIndex] < nums[i]) {
                maxIndex = i;
            }
        }
        //创建根结点
        TreeNode root = new TreeNode(nums[maxIndex]);
        int left_start = start;
        int left_end = maxIndex;

        int right_start = maxIndex + 1;
        int right_end = end;
        root.left = dfs(nums, left_start, left_end);
        root.right = dfs(nums, right_start, right_end);
        return root;
    }

    public static void main(String[] args) {

    }
}
